<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Longest Bitonic Subsequence</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="longest-bitonic-subsequence">Longest Bitonic Subsequence</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=TWHytKnOPaQ&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=37">https://www.youtube.com/watch?v=TWHytKnOPaQ&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=37</a></li>
</ul>
<p>Find longest bitonic subsequence in given array. Bitonic subsequence first increases then decreases.</p>
<p>本题很有意思， 寻找longest bitonic subsequence.  bitonic subsequence 就是先上升，再下降的子序列.</p>
<p>最开始的想法是用两个数组，</p>
<ol>
<li>一个记录以Si结尾的最长上升子序列，</li>
<li>一个记录以Si结尾的最长下降子序列</li>
</ol>
<p>但后面怎么办？  继续不下去了。 看了视频的解法，就是求两次最长上升子序列</p>
<ol>
<li>从左往右扫描的最长上升子序列Li</li>
<li>从右往左扫描的最长上升子序列Ri</li>
</ol>
<p>最后的答案就是 max(Li + Ri - 1)</p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp16.png" alt="dp16.png"></p>

    </body>
    </html>